# 直接拼接
# class Solution(object):
#     def rotate(self, nums, k):
#         """
#         :type nums: List[int]
#         :type k: int
#         :rtype: None Do not return anything, modify nums in-place instead.
#         """
#         length = len(nums)
#         k = k % length
#         return nums[-k:] + nums[:-k]

# 记录位置
# class Solution(object):
#     def rotate(self, nums, k):
#         """
#         :type nums: List[int]
#         :type k: int
#         :rtype: None Do not return anything, modify nums in-place instead.
#         """
#         length = len(nums)
#         k = k % length
#         return_list = nums.copy()
#         for i in range(length):
#             return_list[(i + k) % length] = nums[i]
#         return return_list

# 原地算法
class Solution(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        length = len(nums)
        k = k % length
        t = 1
        total_count = 0
        while total_count < length - 1:
            last_index = length - t
            temp = nums[last_index]
            count = 0
            while (last_index - k * (count + 1)) % length != last_index:
                nums[(last_index - k * count) % length] = nums[(last_index - k * (count + 1)) % length]
                count += 1
            nums[(last_index - k * count) % length] = temp
            total_count += (count + 1)
            t += 1
        return nums


data = Solution()
nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
k = 5
print(data.rotate(nums, k))
